package greddy;

public class _08_134_加油站 {
    public static int canCompleteCircuit(int[] gas, int[] cost) {
    	int curTotal = 0;
    	int total = 0;
    	int start = 0;
    	
    	// 不断计算 +gas[i]-cost[i]的值，如果是负数说明这段路走不了，得从后一个值开始走
    	// 最后一次得到不是负数的i的值(start)，就是起始加油站位置
    	for(int i = 0; i < gas.length; i++) {
    		curTotal = curTotal + gas[i] - cost[i];
    		total = total + gas[i] - cost[i];
    		
    		if(curTotal < 0) {
    			curTotal = 0;
    			start = i + 1;
    		}
    		
    	}
    	// 如果加油和耗油所有值小于0，说明没有一个方案是能走完一圈的
    	if(total < 0) {
    		return -1;
    	} else {
    		return start;
    	}
    	
    }
    
    public static void main(String[] args) {
    	int[] gas = {1,2,3,4,5};
    	int[] cost = {3,4,5,1,2};
    	System.out.println(canCompleteCircuit(gas, cost));
	}
}
